/* ================================================================
*   Copyright (C) 2021 All rights reserved.
*
*   文件名称：xblock_manager.h
*   创 建 者：xunmenglong
*   创建日期：2021年01月23日
*   描    述：
*
================================================================ */


#ifndef XBLOCK_MANAGER_H
#define XBLOCK_MANAGER_H

#include <math.h>
#include <deque>
#include <list>
#include <map>
#include "xio_util.h"
#include "xtime_util.h"

using namespace std;
using namespace xutil;

#define XBLOCK_DEFAULT_UNIT_SIZE 4096           // 4K
#define XBLOCK_DEFAULT_BLOCK_SIZE 536870912     // 512M

/**
 * 一共13万个格子, 将这些格子给管理好, 减小内存碎片
 * 1/2/4/8/...
 * 分配的时候按照指数分配, 将区间内的格子都给管理起来
 * 类似伙伴算法
 */

typedef int (*xblock_iter_func_t)(char * data, int capacity_size, void *arg);

class xblock_manager {
private:
#pragma pack (4)
    struct data_head_t {
        bool is_valid : 1;
        uint  capacity : 31;
    };
#pragma pack()

    struct space_info_t {
        int offset;
        int free_time;
    };

private:
    int _end_offset = 0;            // 如果还没分配完毕, 目前分配到哪儿了
    int _max_unit_num;              // 最大分配的offset
    int _max_unit_exp;
    deque<list<space_info_t>> _space_list;   // 空闲块的指针, 索引是unit_exp
    map<int, int> _start_size_map;  // start_offset->space_size
    map<int, int> _end_size_map;    // end_offset->space_size
    int _unit_size;
    int _block_size;
    char * _data;
    int _free_delay_time;

public:
    int init(const char * file,
                int block_size=XBLOCK_DEFAULT_BLOCK_SIZE,
                int unit_size=XBLOCK_DEFAULT_UNIT_SIZE,
                int free_delay_time=-1,
                xblock_iter_func_t func=NULL,
                void * arg=NULL) {
        _free_delay_time = free_delay_time;
        _unit_size = unit_size;
        _block_size = block_size;
        _max_unit_num = block_size/unit_size;
        _max_unit_exp = _get_exp(_max_unit_num, false);
        _space_list.resize(_max_unit_exp+1);

        _end_offset = 0;
        if (is_file_exists(file)) {
            _data = x_mmap_file(file);
            return load_data(func, arg);
        } else {
            _data = alloc_block(file, block_size);
        }
        return 0;
    }

    int load_data(xblock_iter_func_t func, void * arg) {
        char * _data_ptr;
        int cur_offset = 0;
        while (cur_offset < _max_unit_num) {
            _data_ptr = _data + cur_offset*_unit_size;
            data_head_t * data_head = (data_head_t *)_data_ptr;
            if (data_head->is_valid == true) {
                // 代表有数据需要加载
                char * cur_data = _data_ptr + sizeof(data_head_t);
                if (func != NULL) {
                    int capacity_size = data_head->capacity*_unit_size-sizeof(data_head_t);
                    func(cur_data, capacity_size, arg);
                }
                cur_offset += data_head->capacity;
            } else {
                // 得到当前空间的大小
                int end_offset = cur_offset+1;
                while (end_offset < _max_unit_num) {
                    _data_ptr = _data + end_offset*_unit_size;
                    data_head_t * data_head = (data_head_t *)_data_ptr;
                    if (data_head->is_valid == true) {
                        break;
                    }
                    end_offset += 1;
                }
                if (end_offset >= _max_unit_num) {
                    // 已经是最后了, 将_end_offset设置标记即可
                    break;
                }
                int unit_num = end_offset-cur_offset;
                int next_unit_num = 0;
                int cur_split_offset = end_offset;
                // 将空的格子进行分割
                while (unit_num > 0) {
                    _get_exp(unit_num, false, &next_unit_num);
                    cur_split_offset -= next_unit_num;
                    _add_space(cur_split_offset, next_unit_num);
                    unit_num -= next_unit_num;
                }
                cur_offset = end_offset;
            }
        }
        _end_offset = cur_offset;
        return 0;
    }

    void print_block() {
        char * _data_ptr;
        int cur_offset = 0;
        while (cur_offset < _max_unit_num) {
            _data_ptr = _data + cur_offset*_unit_size;
            data_head_t * data_head = (data_head_t *)_data_ptr;
            if (data_head->is_valid== true) {
                cout << "[";
                for (int i=0; i<data_head->capacity; i++) {
                    cout << cur_offset+i << ", ";
                }
                cout << "]";
                cur_offset += data_head->capacity;
            } else {
                cout << "-" << " ";
                cur_offset += 1;
            }
        }
        cout << endl;
        cout << "end_offset: " << _end_offset << endl
            << "max_unit_num: " << _max_unit_num << endl
            << "max_unit_exp: " << _max_unit_exp << endl;
        cout << "_space_list: " << endl;
        for (int i=0; i<=_max_unit_exp; i++) {
            cout << "\t" << i << ": ";
            for (auto space : _space_list[i]) {
                cout << space.offset << "/";
            }
            cout << endl;
        }
        cout << "_start_size_map: ";
        for (auto v : _start_size_map) {
            cout << "(" << v.first << "/" << v.second << "),";
        }
        cout << endl;
        cout << "_end_size_map: ";
        for (auto v : _end_size_map) {
            cout << "(" << v.first << "/" << v.second << "),";
        }
        cout << endl << "====================" << endl;
    }

    inline int _get_space_offset(int unit_exp) {
        list<space_info_t> & exp_space_list = _space_list[unit_exp];
        if (exp_space_list.size() > 0) {
            space_info_t space = exp_space_list.front();
            int cur_time = get_timestamp();
            if (cur_time - space.free_time >= _free_delay_time) {
                return space.offset;
            }
        }
        return -1;
    }


    /**
     * 优先看后面是否有对应的格子可以用，如果没有，则在全局查找
     *
     * @return NULL代表无法分配; 非NULL代表分配的指针
     */
    char * malloc(int need_size, int * capacity_size) {
        int need_unit_num = ceil((double)(need_size+sizeof(data_head_t))/_unit_size);
        int unit_num;
        int unit_exp = _get_exp(need_unit_num, true, &unit_num);
        if (unit_exp > _max_unit_exp) {
            return NULL;
        }

        // 如果该size下有空闲的单元, 就直接返回
        int space_offset = _get_space_offset(unit_exp);
        if (space_offset >= 0) {
            _del_space(space_offset, unit_num);
            return _get_unit_ptr(space_offset, unit_num, capacity_size);
        }
        // 如果尾巴上还有足够空间, 就直接分配
        if (_end_offset+unit_num <= _max_unit_num) {
            int result_offset = _end_offset;
            _end_offset += unit_num;
            return _get_unit_ptr(result_offset, unit_num, capacity_size);
        }
        // 如果尾巴上空间也不够, 就只能找更大的size下看是否有足够空闲空间
        for (int i=unit_exp+1; i<=_max_unit_exp; i++) {
            list<space_info_t> & cur_space_list = _space_list[i];
            if (cur_space_list.size() > 0) {
                // 就地分配
                space_info_t cur_space = cur_space_list.front();
                int cur_time = get_timestamp();
                if (cur_time - cur_space.free_time >= _free_delay_time) {
                    int first_offset = cur_space.offset;
                    _del_space(first_offset, -1);

                    _split_space_by_exp(first_offset, unit_num, unit_exp, i, cur_space.free_time);

                    return _get_unit_ptr(first_offset, unit_num, capacity_size);
                }
            }
        }
        // 如果也没有更大的空间有剩余的话, 就代表没有空间了, 返回NULL，无法分配
        return NULL;
    }

    /**
     * 尝试直接在当前data往后扩展一倍的空间
     *
     * @param[in] data: 要往后扩展的数据指针地址
     * @param[in] new_size: 用户需求的要扩展的长度
     * @param[out] capacity_size: 返回扩展完毕之后新的容量大小
     */
    bool try_expand_capacity(char * data, int new_size, int * capacity_size) {
        int unit_offset;
        int need_unit_num;
        data_head_t * data_head;
        _get_start_size_map_by_data(data, &unit_offset, &need_unit_num, &data_head);
        int end_offset = unit_offset + need_unit_num;
        if (new_size > need_unit_num*2*_unit_size) {
            // 需要的空间超过了一倍, 就直接返回失败
            return false;
        }

        // 如果正好是最后一个格子的话，就直接分配了
        if (end_offset == _end_offset &&
                _end_offset + need_unit_num <= _max_unit_num) {
            data_head->capacity += need_unit_num;
            _end_offset += need_unit_num;

            *capacity_size = _get_capacity_size(data_head->capacity);
            return true;
        }

        int end_offset_size = _get_space_size_by_startoffset(end_offset);
        if (end_offset_size == -1 || end_offset_size < need_unit_num) {
            // 没有空间或者剩余空间不够, 直接返回
            return false;
        }
        _split_space(end_offset, end_offset_size, need_unit_num);
        data_head->capacity += need_unit_num;
        *capacity_size = _get_capacity_size(data_head->capacity);
        return true;
    }

    /**
     * 释放一块空间, 释放之后可以将前后最合并
     */
    int free(char * data) {
        int unit_offset = 0;
        int unit_num = 0;
        data_head_t * data_head = NULL;
        _get_start_size_map_by_data(data, &unit_offset, &unit_num, &data_head);
        // 标记删除
        data_head->is_valid = false;
        _merge_free_space(unit_offset, unit_num);
        return 0;
    }

private:
    /**
     * 将一块空间的前后剩余空间给合并起来
     */
    int _merge_free_space(int offset, int unit_num) {
        int final_offset = offset;
        int final_unit_num = unit_num;
        while (true) {
            int next_space_offset = final_offset + final_unit_num;
            int next_space_size = _get_space_size_by_startoffset(next_space_offset);
            if (next_space_size == final_unit_num) {
                _del_space(next_space_offset, final_unit_num);
                final_unit_num *= 2;
                continue;
            }
            int before_space_size = _get_space_size_by_endoffset(final_offset);
            if (before_space_size == final_unit_num) {
                final_offset -= final_unit_num;
                _del_space(final_offset, final_unit_num);
                final_unit_num *= 2;
                continue;
            }
            break;
        }
        _add_space(final_offset, final_unit_num);
        return 0;
    }

    void _get_start_size_map_by_data(char * data, int * unit_offset,
            int * unit_num, data_head_t ** data_head_ptr = NULL) {
        char * unit_start_ptr = data - sizeof(data_head_t);
        data_head_t * data_head = (data_head_t *)unit_start_ptr;

        *unit_offset = (int)((unit_start_ptr-_data)/_unit_size);
        *unit_num = data_head->capacity;

        if (data_head_ptr != NULL) {
            *data_head_ptr = data_head;
        }
    }

    char * _get_unit_ptr(int unit_offset, int unit_num, int * capacity) {
        data_head_t * data_head = (data_head_t *)(_data + unit_offset*_unit_size);
        data_head->is_valid = true;
        data_head->capacity = unit_num;
        *capacity = _get_capacity_size(unit_num);
        return (char *)data_head + sizeof(data_head_t);
    }

    // 获得需要返回给用户的容量大小
    inline int _get_capacity_size(int capacity) {
        return capacity*_unit_size - sizeof(data_head_t);
    }

    /**
     * 获取某个数的2的指数
     *
     * 如果unit_num正好是2的指数次方, 则greater指数失效, 直接返回该指数
     * 如果greater为true，则返回>unit_num的第一个指数
     * 如果greater为false，则返回<unit_num的第一个指数
     */
    int _get_exp(int num, bool greater=true, int * out_num=NULL) {
        int tmp_num = 1;
        int exp = 0;
        while (tmp_num < num) {
            tmp_num = tmp_num << 1;
            exp ++;
        }
        if (greater || tmp_num == num) {
            if (out_num != NULL) {
                *out_num = tmp_num;
            }
            return exp;
        }
        if (out_num != NULL) {
            *out_num = tmp_num >> 1;
        }
        return exp-1;
    }

    /**
     * 将一个空间分拆出一个小区块出来
     * 16分2个出来，则变成2,2,4,8
     *
     * @param[in] offset: 待分拆的空间的位置
     * @param[in] capacity: 待分拆空间的大小
     * @param[in] unit_num: 需要拆出去的空间大小
     */
    int _split_space(int offset, int capacity, int unit_num) {
        if (capacity < unit_num) {
            return -1;
        }

        int tmp_unit_num = 1;
        int unit_exp = 0;
        int need_exp = 0;
        while (true) {
            if (tmp_unit_num >= unit_num) {
                need_exp = unit_exp;
            }
            if (tmp_unit_num >= capacity) {
                break;
            }
            tmp_unit_num = tmp_unit_num << 1;
            unit_exp ++;
        }

        int free_time = 0;
        _del_space(offset, capacity, &free_time);
        return _split_space_by_exp(offset, unit_num, need_exp, unit_exp, free_time);
    }

    /**
     * 拆分空间, 配合上面的函数
     *
     * @param[in] offset: 被拆分的空间的位置
     * @param[in] unit_num: 需要拆出去的空间大小
     * @param[in] need_exp: 需要拆出去的空间大小指数
     * @param[in] capacity_exp: 需要拆出去的空间大小指数
     * @param[in] free_time: 被拆分空间的释放时间
     */
    int _split_space_by_exp(int offset, int unit_num, int need_exp, int capacity_exp, int free_time) {
        int gap_offset = 0;
        int cur_split_unit_num = unit_num;
        space_info_t cur_space;
        for (int i=need_exp; i<capacity_exp; i++) {
            gap_offset += cur_split_unit_num;
            int cur_space_start_offset = offset + gap_offset;
            cur_space.offset = cur_space_start_offset;
            cur_space.free_time = free_time;
            _space_list[i].push_back(cur_space);
            _start_size_map.insert(pair<int, int>(cur_space_start_offset, cur_split_unit_num));
            cur_split_unit_num *= 2;
        }
        return 0;
    }

    int _get_space_size_by_startoffset(int offset) {
        map<int, int>::iterator it = _start_size_map.find(offset);
        if (it == _start_size_map.end()) {
            return -1;
        }
        return it->second;
    }

    int _get_space_size_by_endoffset(int offset) {
        map<int, int>::iterator it = _end_size_map.find(offset);
        if (it == _start_size_map.end()) {
            return -1;
        }
        return it->second;
    }

    int _add_space(int start_offset, int unit_num) {
        int end_offset = start_offset + unit_num;
        _start_size_map.insert(pair<int, int>(start_offset, unit_num));
        _end_size_map.insert(pair<int, int>(end_offset, unit_num));
        int unit_exp = _get_exp(unit_num);
        space_info_t cur_space;
        cur_space.offset = start_offset;
        cur_space.free_time = get_timestamp();
        _space_list[unit_exp].push_back(cur_space);
        return 0;
    }

    int _del_space(int start_offset, int unit_num, int * free_time=NULL) {
        if (unit_num == -1) {
            unit_num = _get_space_size_by_startoffset(start_offset);
        }
        _start_size_map.erase(start_offset);
        if (unit_num != -1) {
            int end_offset = start_offset + unit_num;
            _end_size_map.erase(end_offset);
        }
        // 删除链表指针
        int unit_exp = _get_exp(unit_num);
        list<space_info_t> & exp_space_list = _space_list[unit_exp];
        list<space_info_t>::iterator iter;
        for (iter=exp_space_list.begin(); iter != exp_space_list.end(); iter++) {
            if (iter->offset == start_offset) {
                exp_space_list.erase(iter);
                if (free_time != NULL) {
                    *free_time = iter->free_time;
                }
                break;
            }
        }
        return 0;
    }
};

#endif
